package com.practice.sequence;

import java.util.HashMap;

public class LongestRange {
	public int[] longest(int[] a) {
		int start = 0;
		int maxLen = 0;
		
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i=0; i<a.length; i++) {
			int left = map.containsKey(a[i]-1)? map.get(a[i]-1) : 0;
			int right = map.containsKey(a[i]+1)? map.get(a[i]+1) : 0;
			int len = left + 1 + right;
			map.put(a[i]-left, len);
			map.put(a[i]+right, len);
			
			if (len > maxLen) {
				maxLen = len;
				start = a[i] - left;
			}
		}
		
		int[] b = new int[maxLen];
		for (int i=0; i<maxLen; i++) b[i] = start + i;
		return b;
	}
}
